\chapter{Translating AST to HIR}
\label{chap-translating-ast-to-hir}

The translation of an abstract syntax tree
\seechap{chap-abstract-syntax-tree} to high-level intermediate
representation \seechap{chap-ir} is done by an algorithm that is
similar to that of CPS-conversion.%
\footnote{CPS means Continuation Passing Style.}

As with CPS-conversion, translation makes the control structure
explicit.  Another similarity is that translation is done from the end
of the program to the beginning.

\section{\asdf{} system name}

The name of the \asdf{} system that accomplishes the translation of an
abstract syntax tree into HIR is called \texttt{cleavir-ast-to-hir}
and it is located in the file \texttt{cleavir-ast-to-hir.asd} in the
sub-directory named \texttt{AST-to-HIR}.

\section{Package}

The name of the package that contains the names specific to this
system is \texttt{cleavir-ast-to-hir}.  It is defined in the file
named \texttt{packages.lisp} in the sub-directory named
\texttt{AST-to-HIR}.

\section{Compilation context}

Translation of an AST is accomplished with respect to a
\emph{compilation context}.  This context contains a \emph{list of
  lexical variables} to which the values of the translated AST must be
assigned.  The length of the list corresponds to the number of values
required by the context.  The context also contains a \emph{list of
  successors} which represent MIR instructions to which transfer
control after evaluation of the current AST.

\Defclass {context}

This class is the base class for compilation contexts.

\Definitarg {:results}

This initialization argument can be:

\begin{itemize}
\item A list of lexical locations.
\item A single values location.
\end{itemize}

If it is a list, then the number of lexical locations in the list
indicates how many values are required.  The main different cases are:

\begin{itemize}
\item If the list is empty, this means that no values are required.
  Forms inside a \texttt{progn} other than the last one are compiled
  in a context with an empty list of results.  Also, forms used in the
  test form of an \texttt{if} are compiled in a context with an empty
  list of results.
\item If the list is a singleton, then exactly one value is required.
  Arguments to function calls are examples of forms that are compiled
  in a context with a singleton \texttt{results} list.
\item If the list has more than one element, then that many values are
  required.
\end{itemize}

\Defgeneric {results} {context}

This function returns the value that was passed as the
\texttt{:results} initarg when the context was created.

\Definitarg {:successors}

This argument must be a proper list containing zero, one, or two
elements.  These elements are instructions resulting from the
generation of the code that should be executed \emph{after} the code
generated from this AST.

In most cases, this list contains a single element representing the
instruction to which control should be transferred after the execution
of the code resulting from the compilation of the current AST.

Currently, no AST is compiled in a context with zero successors.

If the list contains two elements, then this AST is compiled in a
context where a Boolean result is required.  In this case, the first
element of the list is the successor to use when the value generated
by the AST is \texttt{nil}, and the second element is the successor to
use when the value generated by the AST is something other than
\texttt{nil}.

The \texttt{test-ast} of an \texttt{if-ast} is an example of an AST
that is compiled in a context with two successors.

\Defun {context} {results successors invocation}

This function is deprecated in favor of the function
\texttt{clone-context}.

This function creates a new context, passing the \textit{results}
argument as the \texttt{:results} initarg, the \textit{successors}
argument as the \texttt{:successors} initarg, and the
\textit{invocation} argument as the \texttt{:invocation} initarg.
All other slots of the new context are initialized according to the
\texttt{:initform} of the slot.

\Defun {clone-context} {context \rest arguments}

This function makes a copy of \textit{context} and then calls
\texttt{reinitialize-instance}, passing it the copy and all the
\textit{arguments}.  Here, \textit{arguments} should contain
alternating keywords and keyword arguments that are acceptable for
re-initializing an instance of the class \texttt{context}.  The net
effect is that \textit{context} is cloned with the exception of the
initialization arguments in \textit{arguments}.

The reason for the existence of this function is that it is possible
to add future slots to the class \texttt{context} without breaking
existing code.  Such slots will simply be copied by existing code.
Another reason is that frequently a new context is only slightly
different from some existing context that is available when the new
context must be created.
